📦 dgeee13 / DSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/*
Pattern: Tree Recursion (Take / Not Take)
Approach: Brute Force DFS
State: (node, parentRobbed)
Time Complexity: O(2^n)   // exponential due to overlapping subproblems
Space Complexity: O(h)    // recursion stack, h = tree height
*/
class Solution {
    public:
        int sol(TreeNode* root, bool robbed) {
            if (root == NULL)
                return 0;
            int case_one = 0;
            if (!robbed) {
                case_one =
                    root->val + sol(root->left, true) + sol(root->right, true);
            }
            int case_two = sol(root->left, false) + sol(root->right, false);
            return max(case_one, case_two);
        }
        int rob(TreeNode* root) { return sol(root, false); }
    };



/*
Pattern: Tree DP (Take / Not Take)
Summary: DFS + Memoization (Top-Down)
State: dp[node][parentRobbed]
Time Complexity: O(n)
Space Complexity: O(n)  // recursion stack + DP
*/
class Solution {
    public:
        unordered_map<TreeNode*, array<int, 2>> dp;
        int sol(TreeNode* root, bool robbed) {
            if (root == NULL)
                return 0;
            int idx = robbed ? 1 : 0;
    
            // initialize lazily
            if (!dp.count(root)) {
                dp[root] = {-1, -1};
            }
    
            // correct DP check
            if (dp[root][idx] != -1)
                return dp[root][idx];
            int case_one = 0;
            if (!robbed) {
                case_one =
                    root->val + sol(root->left, true) + sol(root->right, true);
            }
            int case_two = sol(root->left, false) + sol(root->right, false);
            return dp[root][idx] = max(case_one, case_two);
        }
        int rob(TreeNode* root) { return sol(root, false); }
    };